/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
    let r = board.length, c = board[0].length
    const state = new Array(r).fill().map(() => {
        return new Array(c).fill(false)
    })
    const dfs = (i, j, count) => {
        if (count === word.length) return true
        if (i < 0 || i >= r || j < 0 || j >= c) {
            return false
        }
        if (state[i][j] || board[i][j] !== word[count]) {
            return false
        }
        state[i][j] = true
        const yes = dfs(i + 1, j, count + 1) || dfs(i - 1, j, count + 1) || dfs(i, j + 1, count + 1) || dfs(i, j - 1, count + 1)
        if(yes) {
            return true
        }
        state[i][j] = false
        return false
    }
    for (let i = 0; i < r; i++) {
        for (let j = 0; j < c; j++) {
            if (board[i][j] === word[0] && dfs(i, j, 0)) {
                return true
            }
        }
    }
    return false
};